In a random multiple-access communication system, the access operation of channel users is governed by a common discipline called a protocol. The system performance strongly depends on the protocol that the system employs.
Any random access protocol is a contention resolution algorithm. From the viewpoint of information theory, random access protocols can be classified into two categories, the feedback-ignored (FBI) protocols and the feedback--utilized (FBU) protocols. In general, a user who is involved in a collision determines his retransmission moment according to an access protocol. "Feedback-ignored" means that the user's decision on retransmission is independent of the channel activities after the collision. Examples of the FBI protocols are ALOHA, CSMA, CSMA/CD and their derivatives. On the other hand, "feedback-utilized" means that the retransmission decision of a collided packet is dependent on the channel activities after the collision. Examples of the FBU protocols are various types of random splitting protocols, such as the "tree," the "0.487," and the STACK protocols (see G. Gallager, "A perspective on multiaccess channels", IEEE Trans. Inform. Theory, Vol. IT-31, No. 2, pp. 124-142, March 1985).
Protocol performance differs in maximum throughput, delay property and stability. theoretically, FBU protocols can provide better performance than FBI protocols under the same conditions. It has been found that for an infinite population model, all FBI protocols are inherently unstable whereas most of the FBU protocols are stable. However, FBI protocols are relatively simple, well established and widely used. The existing commercial systems using FBI protocols, such as ETHERNET developed by Xerox Corporation (see U.S. Pat. No. 4,063,220 issued Dec. 13, 1977 to Metcalf et al), have met the basic needs of data communication and dominated the market. In contrast, FBU protocols are still in their infancy in practice. The advantages of FBU protocols are not convincing enough to persuade system engineers, who are more concerned for practical details such as standards, compatibility, connectivity, complexity, etc., to use them. Once a system is well--established, other systems, even those offering better performance, have difficulty replacing it.
The need has also arisen for transmitting two types of information such as voice and data, wherein one type of information (e.g. voice) is subject to a delay constraint and therefore has priority over the transmission of the other type of information (e.g. data). See U.S. patent application Ser. No. 770,478 entitled "Packet Switched Local Network with Priority Random Splitting and Conflict Detection" by J. C. Huang and C. L. Yeh filed Aug. 29, 1985.
It is therefore an object of the present invention to improve the performance of existing random multiple access communication systems employing FBI protocols such as ETHERNET, without necessarily replacing existing hardware in such systems. It is a further object of the invention to provide a random multiple--access communication system capable of communicating two types of information such as voice and data, wherein one type of information (e.g. voice) is subject to delay constraints and therefore must possess priority over the other type of information (e.g. data).